package sort;

import java.util.Arrays;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/6 16:03
 */
public class ShellSort {
    public static void shellSort(long[] array) {
        if (array.length == 0) {
            return;
        }
        int gap = array.length / 2;//10
        while (true) {
            // 带有间隔的分组插排
            for (int i = gap; i < array.length; i++) {//10 11
                long x = array[i];//arr10 11
                int j;//0 1
                for (j = i - gap; j >= 0 && array[j] > x; j = j - gap) {//0>arr10
                    array[j + gap] = array[j];
                }

                array[j + gap] = x;//arr0=arr10
            }

            if (gap == 1) {
                // 说明上一次的分组插排其实最终的插排
                break;
            }

            gap = gap / 2;
        }
    }
    public static void main(String[] args) {
        long[] array = {31, 6, 0, 48, 46, 6, 15, 46, 11, 31, 38, 12, 41, 43, 20, 38, 49, 24, 6, 6};
        shellSort(array);

        System.out.println(Arrays.toString(array));
    }
}
